/**
 * @Author: XJH
 * @Description: TODO
 * @Date: 2025/10/21 21:33
 * @Version: 1.0
 */

import java.util.HashSet;
import java.util.Set;

/**
 * @Author: XJH
 * @Description: TODO
 * @Date: 2025/10/21 21:33
 * @Version: 1.0
 * 128. 最长连续序列
 * 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
 * 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
 */
public class Longest_continuous_sequence {
    public int longestConsecutive(int[] nums) {
        Set<Integer> st = new HashSet<>();
        for(int num:nums){
            st.add(num);
        }
        //假设 nums = [5, 1, 3, 10, 2, 9]，对应的哈希集合是 {1,2,3,5,9,10}。
        int ans=0;
        int m=st.size();
        for(int x:st){
            if(st.contains(x-1)){//如果 x-1 存在于集合中，说明 x 不是序列的起点（前面还有连续的数）
                continue;//跳到下一次循环
            }
            int y=x+1;
            while(st.contains(y)){
                //当条件未成立，y是第一个不在集合里面的数
                // 循环结束后，y-1 是最后一个在哈希集合中的数
                y++;
            }
            ans=Math.max(ans,y-x);// 从 x 到 y-1 一共 y-x 个数
            if(ans*2>=m){
                break;
            }
        }
        return ans;
    }
    public static void main(String[] args) {
        int[] nums = {5, 1, 3, 10, 2, 9};
        Longest_continuous_sequence lcs = new Longest_continuous_sequence();
        int result = lcs.longestConsecutive(nums);
        System.out.println(result);
    }
}
